package LiKouBrushQuestions;

public class June_28 {
    public static void main(String[] args) {
        System.out.println("虽千万难，吾亦愿往！");
    }
}

/**
 * 旋转数组的最小数字
 *
 * @time 6.28
 */
class SolutionMinArray {
    public int minArray(int[] numbers) {
        int[] ReversionArray = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            ReversionArray[numbers.length - i] = numbers[i];
        }
        int min = ReversionArray[1];
        for (int i = 1; i <= numbers.length; i++) {
            if (ReversionArray[i] < min) {
                min = ReversionArray[i];
            }
        }
        return min;
    }
}

/**
 * @author 23737
 * @time 6.28
 */
class SolutionReplace {
    public String replaceSpace(String s) {
        //调用库函数毫无意义，这种做法取消
//        return s.replace(" ","%20");
        StringBuilder stringBuffer = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                stringBuffer.append("%20");
            } else {
                stringBuffer.append(c);
            }
        }
        return stringBuffer.toString();
    }
}

/**
 * @author 23737
 * @time 6.29   0.32
 */
class SolutionFindNumber {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (target == ints[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * @author 23737
 * @time 6.29  0.40
 * 剑指offer 12
 */
//回朔法
class SolutionPathIn2Array {
    public boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0 || board == null || word == null) { // 判断是否为空, 为空则直接返回false
            return false;
        }
        int rows = board.length;  // 行数
        int cols = board[0].length; // 列数
        int k = 0; // k = 0 表示目前找到的字符数为0, 找到一个匹配的字符则 k + 1
        int[][] dp = new int[rows][cols]; // 用dp数组判断是否走过, 若为0, 则说明未走过, 若 > 0, 则说明这个格子被走过, 不能再走

        for (int i = 0; i < rows; i++) { // 用双循环先找到第一个字符, 然后根据第一个字符去寻找第二个字符
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(k)) {
                    dp[i][j]++;
                    if (k == word.length() - 1 || searchAround(i, j, k + 1, board, word, dp)) {
                        // k != word.length(),说明还未找全字符, 调用searchAround方法, 寻找下一个字符
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static boolean searchAround(int i, int j, int k, char[][] board, String word, int[][] dp) {
        // 往上搜索
        if (i - 1 >= 0 && dp[i - 1][j] == 0 && board[i - 1][j] == word.charAt(k)) {
            // 不越界 && 可以走 && 找到相应的字符
            dp[i - 1][j] = dp[i][j] + 1; // 可以根据数组元素大小顺序模拟出路径
            if (k == word.length() - 1 || searchAround(i - 1, j, k + 1, board, word, dp)) {
                return true;
            }
        }
        // 往下搜索
        if (i + 1 < board.length && dp[i + 1][j] == 0 && board[i + 1][j] == word.charAt(k)) { // 不越界 && 可以走 && 找到相应的字符
            dp[i + 1][j] = dp[i][j] + 1; // 可以根据数组元素大小顺序模拟出路径
            if (k == word.length() - 1 || searchAround(i + 1, j, k + 1, board, word, dp)) {
                return true;
            }
        }
        // 往左搜索
        if (j - 1 >= 0 && dp[i][j - 1] == 0 && board[i][j - 1] == word.charAt(k)) { // 不越界 && 可以走 && 找到相应的字符
            dp[i][j - 1] = dp[i][j] + 1; // 可以根据数组元素大小顺序模拟出路径
            if (k == word.length() - 1 || searchAround(i, j - 1, k + 1, board, word, dp)) {
                return true;
            }
        }

        // 往右搜索
        if (j + 1 < board[0].length && dp[i][j + 1] == 0 && board[i][j + 1] == word.charAt(k)) { // 不越界 && 可以走 && 找到相应的字符
            dp[i][j + 1] = dp[i][j] + 1; // 可以根据数组元素大小顺序模拟出路径
            if (k == word.length() - 1 || searchAround(i, j + 1, k + 1, board, word, dp)) {
                return true;
            }
        }
        dp[i][j] = 0; // 重新将dp[i][j]赋值为0, 表明这个格子行不通且未被走过
        return false; // 往四个方向都未找到对应字符, 直接返回false
    }
}



